package com.leetcode.LeetCode精选TOP面试题;

import com.leetcode.common.model.ListNode;

/**
 * @author 覃国强
 * @date 2022-05-18 19:04
 */
public class 题库_0019_删除链表的倒数第N个结点 {

  static
  class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
      ListNode dummy = new ListNode();
      dummy.next = head;

      // 使哨兵向前走 n 步，及哨兵距离头 n 个节点
      ListNode sentinel = head;
      while (n > 0) {
        if (sentinel == null) {
          return head;
        }
        sentinel = sentinel.next;
        --n;
      }

      // prev 和哨兵同时向前走，当哨兵到达末尾时，prev 距离尾节点 n 步
      ListNode prev = dummy;
      while (sentinel != null) {
        prev = prev.next;
        sentinel = sentinel.next;
      }

      // 执行删除操作
      ListNode delete = prev.next;
      prev.next = delete.next;
      delete.next = null;

      return dummy.next;
    }
  }

}
